package find;

public class EnhancedBinarySearch {

    private static int findFirstEqualPos(int[] arrSrc, int n) {
        int iStart = 0;
        int iEnd = arrSrc.length - 1;

        while (iStart <= iEnd) {
            int iMid = iStart + (iEnd - iStart) / 2;

            if (arrSrc[iMid] > n) {
                iEnd = iMid - 1;
            } else if (arrSrc[iMid] < n) {
                iStart = iMid + 1;
            } else {
                //当 iMid == 0 时，表示为数组的第一个，当他前一个数据不等于n时，他就是第一个
                if (iMid == 0 || arrSrc[iMid - 1] != n) {
                    return iMid;
                } else {
                    iEnd = iMid - 1;
                }
            }
        }

        return -1;
    }

    private static int findLastEqualPos(int[] arrSrc, int n) {
        int iStart = 0;
        int iEnd = arrSrc.length - 1;

        while (iStart <= iEnd) {
            int iMid = iStart + (iEnd - iStart) / 2;
            if (arrSrc[iMid] > n) {
                iEnd = iMid - 1;
            } else if (arrSrc[iMid] < n) {
                iStart = iMid + 1;
            } else {
                //当 iMid == 长度-1时，表示为数组的最后一个，当他后一个数据不等于n时，他就是最后一个
                if (iMid == arrSrc.length - 1 || arrSrc[iMid + 1] != n) {
                    return iMid;
                } else {
                    iStart = iMid + 1;
                }
            }
        }

        return -1;
    }

    private static int findFirstGreatOrEqualPos(int[] arrSrc, int n) {
        int iStart = 0;
        int iEnd = arrSrc.length - 1;
        while (iStart <= iEnd) {
            int iMid = iStart + (iEnd - iStart) / 2;

            if (arrSrc[iMid] >= n) {
                //当 IMid 为0时，表示为最小的坐标，当 iMid - 1 位置的值小于 n 时，表示 iMid 就是第一个大于等于 n 的位置
                if (iMid == 0 || arrSrc[iMid - 1] < n) {
                    return iMid;
                } else {
                    iEnd = iMid - 1;
                }
            } else {
                iStart = iMid + 1;
            }
        }

        return -1;
    }

    private static int findLastLessOrEqualPos(int[] arrSrc, int n) {
        int iStart = 0;
        int iEnd = arrSrc.length - 1;

        while (iStart <= iEnd) {

            int iMid = iStart + (iEnd - iStart) / 2;
            if (arrSrc[iMid] <= n) {
                if (iMid == arrSrc.length - 1 || arrSrc[iMid + 1] > n) {
                    return iMid;
                } else {
                    iStart = iMid + 1;
                }
            } else {
                iEnd = iMid - 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arrSrc = new int[] {1,3,5,5,6,6,6,7,8,9,12};
        System.out.println("first equal pos : " + findFirstEqualPos(arrSrc, 5));
        System.out.println("last equal pos : " + findLastEqualPos(arrSrc, 5));
        System.out.println("first greater or equal pos : " + findFirstGreatOrEqualPos(arrSrc, 6));
        System.out.println("last less or equal pos : " + findLastLessOrEqualPos(arrSrc, 6));
    }

}
